package util;

import graph.DirectedEdge;
import graph.Graph;
import graph.Graph.Edge;
import graph.MultiGraph;
import graph.Tree;
import graph.TreeImplement;
import java.util.ArrayList;
import java.util.Random;

/**
 * Create random tree graph-based
 *
 * @author DO Ngoc Cuong
 */
public class RandomTree {

    /**
     * Create a random tree from a long seed
     *
     * @param numNodes The number of nodes of tree
     * @param seed Used to create a new random number generator using a long
     * seed
     * @return
     */
    public static Tree<Integer, Graph.Edge<Integer>> create(int numNodes, long seed) {
        return create(numNodes, seed, 0);
    }

    public static Tree<Integer, Graph.Edge<Integer>> create(int numNodes, long seed, int root) {
        if (numNodes <= 2) {
            throw new IllegalArgumentException(
                    "The number of nodes must be greater than 2.");
        }
        int[] sequence = randomSequence(numNodes - 2, seed);
        return create(sequence, root);
    }

    public static Tree<Integer, Graph.Edge<Integer>> create(int[] sequence, int root) {
        Graph<Integer, Graph.Edge<Integer>> tree = pruferToTree(sequence);
        setRoot(tree, root, -1);
        return new TreeImplement<Integer, Graph.Edge<Integer>>(tree, root);
    }

    /**
     * Convert a Prufer sequence into a tree graph-based
     *
     * @param sequence Prufer sequence
     * @return Tree graph-based
     */
    private static Graph<Integer, Graph.Edge<Integer>> pruferToTree(
            int[] sequence) {

        if (sequence == null || sequence.length == 0) {
            throw new IllegalArgumentException("Invalid Prufer sequence.");
        }

        // number of tree nodes
        int numNodes = sequence.length + 2;

        // create graph with isolated nodes, numbered from 0 to numNodes - 1
        MultiGraph<Integer, Graph.Edge<Integer>> g = new MultiGraph<Integer, Graph.Edge<Integer>>();
        for (int i = 0; i < numNodes; i++) {
            g.addVertex(i);
        }

        // node's degree
        int[] degree = new int[numNodes];

        // for each node set its degree to the number of times it appears in the
        // sequence plus 1
        for (int v : sequence) {
            degree[v]++;
        }

        for (int u : sequence) {
            for (int v = 0; v < numNodes; v++) {
                // find the node with degree = 0
                if (degree[v] == 0) {
                    // add the edge (u, v) to the tree and decrease the degree
                    // of u and v
                    addTreeEdge(g, degree, u, v);
                    break;
                }
            }
        }

        // find the last 2 nodes have degree = 0
        int u = -1, v = -1;
        for (int i = 0; i < numNodes; i++) {
            if (degree[i] == 0) {
                if (u == -1) {
                    u = i;
                } else {
                    v = i;
                    break;
                }
            }
        }
        // add the last edge between 2 found nodes
        addTreeEdge(g, degree, u, v);
        return g;
    }

    /**
     * Generate random Prufer sequence with seed number
     *
     * @param length The length of sequence
     * @param seed Used to create a new random number generator using a long
     * seed
     * @return Integer array represents Prufer sequence
     */
    private static int[] randomSequence(int length, long seed) {
        Random random = new Random(seed);
        int[] a = new int[length];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(a.length);
        }
        return a;
    }

    private static void addTreeEdge(Graph<Integer, Graph.Edge<Integer>> g,
            int[] degree, int u, int v) {
        // add directional edges into graph
        g.addEdge(new DirectedEdge<Integer>(u, v));
        g.addEdge(new DirectedEdge<Integer>(v, u));
        // decrease degree of each node
        degree[u]--;
        degree[v]--;
    }

    /**
     * Find the first vertex that has 0 indegree
     *
     * @param graph Input graph
     * @return The vertex as integer value has 0 indegree or -1 if not
     */
    private static int findRoot(Graph<Integer, Graph.Edge<Integer>> graph) {
        if (!Graphs.isTree(graph)) {
            throw new IllegalArgumentException("The graph is not a tree");
        }
        for (Integer v : graph.vertices()) {
            if (graph.indegree(v) == 0) {
                return v;
            }
        }
        return -1;
    }

    private static void setRoot(Graph<Integer, Graph.Edge<Integer>> graph, int root, int parent) {
        if (!graph.containsVertex(root)) {
            throw new IllegalArgumentException("Invalid root");
        }

        ArrayList<Edge<Integer>> incommingEdges = new ArrayList<Edge<Integer>>();
        for (Graph.Edge<Integer> edge : graph.incomingEdges(root)) {
            if (edge.source() != parent) {
                incommingEdges.add(edge);
            }
        }
        graph.removeAllEdges(incommingEdges);

        ArrayList<Integer> outgoingVertices = new ArrayList<Integer>();
        for (Graph.Edge<Integer> edge : graph.outgoingEdges(root)) {
            outgoingVertices.add(edge.target());
        }
        for (Integer v : outgoingVertices) {
            setRoot(graph, v, root);
        }
//        System.out.println(graph);
    }

}
